package algotithm.weekendrace.leetcode244.test4;

import java.util.Arrays;

/**
 * @author 25068
 * @Date 2021/6/6 12:16
 * @Title 5779. 装包裹的最小浪费空间
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] p = {2,3,5};
        int[][] boxes = {{4,8},{2,8}};
        int res = solution.minWastedSpace(p, boxes);
        System.out.println(res);
    }

    final int N = 100000;
    long MOD = (int) 1e9 + 7;
    public int minWastedSpace(int[] p, int[][] boxes) {
        int n = p.length;
        long ans = Long.MAX_VALUE;
        Arrays.sort(p);
        long[] cnt = new long[N + 10], sum = new long[N + 10];
        for(int i : p) {
            cnt[i]++;
            sum[i] += i;
        }
        for(int i = 1; i <= N; i++) {
            cnt[i] += cnt[i - 1];
            sum[i] += sum[i - 1];
        }
        for(int[] b : boxes) {
            Arrays.sort(b);
            int m = b.length;
            if(b[m - 1] < p[n - 1]) {
                continue;
            }
            long res = (long) n * b[m - 1] - sum[N];
            for(int i = m - 2; i >= 0; i--) {
                res -= (b[i + 1] - b[i]) * cnt[b[i]];
            }
            ans = Math.min(ans, res);
        }
        return ans == Long.MAX_VALUE ? -1 : (int)(ans % MOD);
    }
}